home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Cream of the Crop 1
/
Cream of the Crop 1.iso
/
PROGRAM
/
BFSORTS.ARJ
/
MSORT.C
< prev
next >
Wrap
C/C++ Source or Header
|
1991-03-31
|
4KB
|
142 lines
/***********************************************************************/
/* SORT(): Non-Recursive Merge Sort function. */
/* See the function declaration for calling information. */
/* Function is by Bruce Feist; please contact me on CompuServe with */
/* a message on BPROGB, MACDEV, or EASYPLEX if you have any */
/* questions or problems. */
/* You can also reach me at the Enlightened Board, at (703) 370-9528, */
/* N/8/1 */
/* Feel free to make use of this code in your own programs. */
/***********************************************************************/
/* Merge sort. Fast, but uses lots of space. */
#include <alloc.h>
#include <mem.h>
#include <stddef.h>
#include <stdio.h>
#include "sort.h"
#define VERBOSE (0)
static char *base, *last_ptr, *temp_base;
static unsigned int nelem, width;
static int (*compare) (void *, void *);
static void merge (char *, unsigned int);
#if VERBOSE
static void show_array (void *, int);
#endif
int
msort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())
{
long sublist_length, sublist_offset;
unsigned int list_size;
base = pbase;
nelem = pnelem;
width = pwidth;
compare = pcompare;
#if VERBOSE
printf ("Msort (%p, %d, %d, %p).\n", pbase, pnelem, pwidth, pcompare);
#endif
list_size = nelem * width;
temp_base = malloc (list_size);
if (temp_base == NULL)
return S_NOMEM;
last_ptr = base + list_size - width;
/* We first merge sublists of length 1, then of length 2, and */
/* so on, doubling each time. */
for (sublist_length = width;
sublist_length < list_size;
sublist_length <<= 1)
{
for (sublist_offset = 0;
sublist_offset + sublist_length < list_size;
sublist_offset += sublist_length << 1)
#pragma warn -sig
merge (base + sublist_offset, (unsigned int) sublist_length);
#pragma warn .sig
} /* for sublist_length */
free (temp_base);
return S_OK;
} /* end msort */
void
merge (char *left_base, unsigned int length)
{
char *left_ptr, *right_ptr, *left_max, *right_max, *result_ptr;
#if VERBOSE
printf ("Merge (%p, %u)\n", left_base, length);
#endif
left_ptr = left_base;
right_ptr = left_base + length;
left_max = right_ptr - width;
right_max = (length > last_ptr - right_ptr) ? last_ptr : left_max + length;
#if VERBOSE
fputs ("Input: ", stdout);
show_array (left_base, (right_max - left_base + width) / sizeof (double));
if (length > 20000)
printf ("Merging %p - %p with %p - %p.\n",
left_ptr, left_max, right_ptr, right_max);
#endif
result_ptr = temp_base;
while (1)
{
if (compare (left_ptr, right_ptr) > 0)
{
memcpy (result_ptr, right_ptr, width);
right_ptr += width;
result_ptr += width;
if (right_ptr > right_max)
{
memcpy (result_ptr, left_ptr, left_max - left_ptr + width);
break;
}
}
else
{
memcpy (result_ptr, left_ptr, width);
left_ptr += width;
result_ptr += width;
if (left_ptr > left_max)
{
memcpy (result_ptr, right_ptr, right_max - right_ptr + width);
break;
}
}
} /* end while */
#if VERBOSE
printf ("Copying %d bytes from %p to %p.\n",
right_max - left_base + width, temp_base, left_base);
fputs ("Intermediate: ", stdout);
show_array (temp_base, (right_max - left_base + width) / sizeof (double));
#endif
memcpy (left_base, temp_base, right_max - left_base + width);
#if VERBOSE
fputs ("Output: ", stdout);
show_array (left_base, (right_max - left_base + width) / sizeof (double));
#endif
} /* end merge */